\documentclass[submission]{FPSAC2017}

\articlenumber{56}
\addbibresource{56_Corteel_Nunge.bib}

\usepackage{lipsum}
\usepackage{tikz}

\usepackage{physics}
\usepackage{bm}
\usepackage{graphicx}
\usepackage{todonotes}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{algo}{Algorithm}

%%%%%%%%%% Algebres %%%%%%%%%%%%
\def\SCQSym{{\bf SCQSym}}      % Algebre des 3^n (quotient de SQSym^*)
\def\NCSF{{\bf Sym}}           % NCSF
\def\FQSym{{\bf FQSym}}        % permutations
\def\SFQSym{{\bf FQSym^{(2)}}}        % permutations signees
\def\GPQSym{{\bf PSQSym}}      % gap permutations

\def\SG{{\mathfrak S}}  % groupe symmetrique
\def\RSC{{\it R}}       % fonctions R des compositions segmentees
\def\FGP{{\it F}}       % fonctions F des permutations a trous
\def\FSP{{\bf F}}       % fonctions F des permutations signees
\def\Ig{{\bf I}}        % I gras
\def\Jg{{\bf J}}        % J gras
\def\ie{{\emph i.e.}}   % i.e.
\def\ssig{{\bm \sigma}} % sigma gras
\def\ttau{{\bm \tau}}   % tau gras

\def\Des{\operatorname{Des}}   % ensemble de descente d'une composition
\def\GDes{\operatorname{GDes}} % ensemble de descente de Genocchi
\def\RecSet{\operatorname{RecSet}} % ensemble de descente de Genocchi
\def\GC{\operatorname{GC}}     % composition de descente de Gennochi
\def\Rec{\operatorname{Rec}}   % reculs
\def\tto{{\rm tot}}            % nombre de motifs 31-2
\def\Std{{\rm Std}}            % standardise
\def\ade{{\rm ade}}            % seg compo to ADE-word
\def\312{31\!-\!2}

\def\sconc{\bullet}     % concatenation shiftee
\def\ssh{\Cup}          % shuffle shifte

\def\shuff#1#2{\mathbin{
    \hbox{\vbox{ \hbox{\vrule \hskip#2 \vrule height#1 width 0pt
        }%
        \hrule}%
      \vbox{ \hbox{\vrule \hskip#2 \vrule height#1 width 0pt
          \vrule }%
        \hrule}%
}}}

\def\binomial#1#2{\left(\,\begin{matrix}#1 \cr #2\end{matrix}\,\right)}
\def\binomial#1#2{\binom{#1}{#2}}

\def\shuf{{\mathchoice{\shuff{7pt}{3.5pt}}%
    {\shuff{6pt}{3pt}}%
    {\shuff{4pt}{2pt}}%
    {\shuff{3pt}{1.5pt}}}}%
\def\shuffle{\,\shuf\,}

\def\sty{\displaystyle}

\title{2-species exclusion processes and combinatorial algebras}

\author{Sylvie Corteel\addressmark{1}\thanks{\href{mailto:corteel@irif.fr}{corteel@irif.fr}}
  \and Arthur Nunge\addressmark{2}\thanks{\href{arthur.nunge@u-pem.fr}{arthur.nunge@u-pem.fr}}}

\address{\addressmark{1}IRIF, CNRS et Universit\'e Paris Diderot, Case 7014, 75205 Paris Cedex 13, France\\
  \addressmark{2}LIGM, Universit\'e Paris-Est
  Marne-la-Vall\'ee, 5 Boulevard Descartes, Champs-sur-Marne, France}

\received{\today}

\abstract{Starting from the two-species asymmetric simple exclusion process, we study
  a subclass of signed permutations, the partially signed permutations,
  using the combinatorics of Laguerre histories. From this physical
  and bijective point of view, we obtain natural recoil and descent statistics on partially signed permutations.
  We define a new
  combinatorial algebra on these partially signed permutations and show that the segmented composition algebra
  defined by Novelli and Thibon is a
  subalgebra of this new algebra. This new point of view allows us to define a new basis for the segmented
  composition algebra
  with combinatorial properties. This generalizes classical combinatorial 
  results on permutation and composition algebras.}

\keywords{Exclusion processes, bijections, matrix Ansatz, non commutative symmetric functions,
signed permutations, algebras}


\begin{document}

\maketitle

\section{Introduction}

The two-species asymmetric simple exclusion process (2-ASEP) is a Markov chain with two
types of particles (1 and 2) and holes (0). Particles can hop to the right and to the left and
particles of type 2 can enter and exit the system. If there are no particles of type 1, we recover
the classical ASEP.
See \cref{secPASEP}
and~\cite{uchiyama} for a detailed definition.
The stationary distribution of the 2-ASEP gives rise to some interesting combinatorics~\cite{CMW, MV, MV1}.
In this paper, we interpret it as some generalization of Laguerre histories defined
by Fran\c{c}on and Viennot~\cite{FV}: the {\em marked Laguerre histories}.
We give a bijection between the {marked Laguerre histories}
and a subclass of signed permutations where we do not put a sign on 1. We call them partially signed permutations.
For example, the partially signed permutations of size 2 are
$12$, $21$, $1\overline{2}$ and $\overline{2}1$. We denote by $B_n$ the set of signed permutations of size $n$ and by $B_n'$ the set of partially signed permutations.
The natural statistic coming from the 2-ASEP define a statistic
on a partially signed permutation $\ssig $: the \emph{Genocchi composition} $GC(\ssig)$ and the notion
of {\em patterns} of a partially signed permutation, here the number of occurrences of the pattern $\312$ and of
the pattern $(31,\overline{2})$. Indeed, the $\GC$ statistic encodes the state of the Markov chain
and the patterns are related to its transition rates.
This is related to some combinatorial work of Mandelshtam and Viennot who
defined rhombic alternative tableaux~\cite{MV1}.
Let us define a segmented composition $\Ig$ of $n$ as a finite sequence of positive integers of sum $n$
separated by vertical bars or commas. For example, $(1|2|1,2,2)$
is a segmented composition of 8.
\begin{thm}
  Given $\Ig$ a segmented composition of $n$, the quotient
  \begin{equation}
    \frac{\displaystyle \sum_{\sigma \in B_n', \GC(\sigma)=\Ig}q^{\#_{\312}(\sigma)+\#_{(31,\overline{2})}(\sigma)}}
         {\displaystyle \sum_{\sigma \in B_n'}q^{\#_{\312}(\sigma)+\#_{(31,\overline{2})}(\sigma)}}
  \end{equation}
  is the stationary distribution of the state of the 2-ASEP coded by the segmented composition $\Ig$.
  \label{probaPerm}
\end{thm}
Here $\#_p(\sigma)$ denotes the number of occurrences of the pattern $p$ in $\sigma$.
Our work here also gives a ``permutation'' interpretation of the $q$-statistic
that was missing from~\cite{MV}.

Next we generalize the algebra~$\FQSym$~\cite{FQSYM} and propose an algebra on $B'$ that we
call $\GPQSym$.
The fundamental basis $\FGP_\ssig$ for $\ssig\in B'$ has a natural product $\Cup$,
the shifted shuffle product.
\begin{proposition}
  Given $\ssig$ and $\ttau$ two elements of $B'$, we have
  \begin{equation}
  \FGP_\ssig \cdot \FGP_\ttau=\sum_{\bm{\mu}\in\ssig\Cup \ttau}\FGP_{\bm{\mu}}.
  \end{equation}
  \label{producFormula}
\end{proposition}


We continue the analogy and show that the segmented composition algebra $\SCQSym$ defined in~\cite{NT} 
is a subalgebra of $\GPQSym$. In order to do this, we need the notion of the {\em recoils} of a partially signed permutation.
We show that the ribbon basis $\RSC_\Ig$ defined in~\cite{NT} can be written as follows~:
\begin{proposition}
  Let $\Ig$ be a segmented composition, we have
  \begin{equation}
    \RSC_\Ig=\sum_{\ssig \in B';~ \Rec(\ssig)=I} \FGP_\ssig.
  \end{equation}
  \label{injRF}
\end{proposition}

We then define a new basis $L_\Ig$ of $\SCQSym$ that is an analogue of the fundamental basis of Tevlin defined
in~\cite{T}.
This basis comes from a projection of $\GPQSym$ to $\SCQSym$ generalizing~\cite{HNTT}.
We define an equivalence relation on partially signed permutations where two signed permutations
are equivalent if and only if their $GC$ statistics are the same. We quotient  $\GPQSym$ by this
equivalence relation and define the basis $L_\Ig$ as the image of $\FGP_\ssig$ by this quotient.
This basis, like the basis defined by Tevlin, has structure coefficients equal to binomial coefficients.
This is \cref{thCoeff} in \cref{algebre}.

Finally, we exhibit the change of basis between the bases $R_\Ig$ and $L_{\bf J}$ and show
in \cref{thChangeBasis} that
the coefficients are positive integers and give a combinatorial interpretation in terms
of partially signed permutations with fixed $GC$ and recoils.

All the detailed definitions will be given in \cref{defi}. In \cref{secPASEP}, we give
the idea of the proof of \cref{probaPerm} using Laguerre histories.
In \cref{algebre} we give the algebraic results in detail.


\section{Notations and definitions}
\label{defi}

\subsection{Signed permutations and segmented compositions}

A \emph{signed permutation} $\ssig$ of size $n$ is a permutation of $n$ such that
each value has a sign plus or minus. We denote by $B_n$ the set of signed permutations
of size $n$.
We overline negative values and we say that $\overline{i} \in \ssig$
if the value $i$ has a negative sign in $\ssig$. For example,
$\ssig = \overline{2}57836\overline{4}1$ is a signed permutation of size $8$.

When we compare two values $\ssig_i$ and $\ssig_j$ of a signed permutation
$\ssig$, we use the order $\overline{1} < 1 < \overline{2} < 2 <  \cdots$.

In this paper we consider the set of signed permutations where $1$ is not signed, which
we call \emph{partially signed permutations}. We
denote by $B_n'$ the set of these permutations.
For example, $\ssig= \overline{2}57836\overline{4}1$ is an element of $B_n'$.

A $\312$ pattern of $\ssig$ is a pair $(\sigma_i\sigma_{i+1},\sigma_j)$ such that $j > i+1$ 
and $\ssig_{i} > \ssig_j > \ssig_{i+1}$. We also consider $(31,\overline{2})$ patterns that
are pairs $(\sigma_i\sigma_{i+1},\overline{k})$ such that $\overline{k} \in \ssig$ and
$\ssig_{i} \geq \overline{k}> \ssig_{i+1}$. Note that in the second case the value $\overline{k}$
is not necessarily to the right of $\sigma_i$. For example, the  $\312$
patterns of $\ssig = \overline{2}57836\overline{4}1$ are (83,6) and $(83,\overline{4})$ and
the $(31,\overline{2})$ patterns of $\ssig$ are 
$(83, \overline{4})$, $(\overline{4}1,\overline{2})$, and $(\overline{4}1, \overline{4})$).

A \emph{segmented composition}~\cite{NT} of an integer $n$ is a finite sequence
$\Ig$ of $\ell$ positive integers $(i_1,\ldots ,i_\ell)$ that sum to $n$
separated by vertical bars or commas.
The \emph{descent set} of $\Ig$ is the set of signed values
$\Des(\Ig) = \{ i_1,\ i_1+i_2, \ldots , i_1+\dots+i_{\ell-1}\}$ where
$i_1+i_2+\ldots+i_k$ is overlined if and only if there is a bar after
$i_k$ in $\Ig$. For example, $\Des(1|2|1,2,2) = \{\overline{1},\overline{3}, 4, 6\}$.
The \emph{ADE-word} associated with $\Ig$ is the word $w$ of
size $n-1$ such that
\begin{equation}
  \begin{array}{rcl}
    \overline{i} \in \Des(\Ig) & \Rightarrow & w_i = A; \\
    i \in \Des(\Ig) & \Rightarrow & w_i = E; \\
    \overline{i} \notin \Des(\Ig), i \notin \Des(\Ig) & \Rightarrow & w_i = D.
  \end{array}
  \label{ade}
\end{equation}
We denote this word by $\ade(\Ig)$. For example,
$\ade(1|2|1,2,2) = ADAEDED$.

Let $\ssig \in B_n'$.
Define the \emph{recoil set} of $\ssig$ as
\begin{equation}
  \RecSet(\ssig) := \{i~|~\ssig_k\in\{i,\overline{i}\},~ \ssig_j=i+1 \Rightarrow j < k~\}
  \cup \{\overline{i-1}~|~\overline{i} \in \ssig\}.
\end{equation}
Note that if $\ssig$ has no negative values then $\RecSet(\ssig)$ exactly
corresponds to the set of values
$i$ such that $i+1$ is to its left, which is the usual definition of the recoil set
on permutations.

The {\em recoil composition} $\Rec(\ssig)$ is the segmented composition whose descent set is $\RecSet(\ssig)$.
For example, if $\ssig = \overline{2}57836\overline{4}1$ we have
$\RecSet(\ssig)=\{\overline{1},\overline{3},4,6\}$ and $\Rec(\ssig)=(1|2|1,2,2)$.

Define the \emph{Genocchi descent set} of a partially signed permutation $\ssig$ of size $n$ as
\begin{equation}
  \GDes(\ssig) := \{i-1~|~\ssig_j = i \Rightarrow \ssig_j > \ssig_{j+1}\}
  \cup \{\overline{i-1}~|~\overline{i} \in \ssig\}.
\end{equation}
Define the \emph{Genocchi composition of descents} $\GC(\ssig)$ as the
segmented composition $\Ig$ whose descent set is  $\GDes(\ssig)$.
If $\ssig$ is a permutation, the statistic $\GC$ is the set of values of descents minus one, as
in~\cite{HNTT}.
For example, if $\ssig = \overline{2}57836\overline{4}1$, we have
$\GDes(\ssig)=\{\overline{1},\overline{3},5,7\}$ and
$\GC(\ssig)=(1|2|2,2,1)$.

\begin{proposition}
  We have $\overline{i}\in \GDes(\sigma)$ if and only if $\overline{i}\in \RecSet(\sigma)$.
  \label{remNbA}
\end{proposition}

\section{2-ASEP, Matrix Ansatz and Laguerre histories}
\label{secPASEP}



The two-species ASEP is a Markov chain whose states are words of length $N$ in the letters
$\{0,1,2\}$. This was first studied in a more general setting in~\cite{uchiyama}
and then in~\cite{CMW,MV1}. Let $x$ and $y$ arbitrary words in $\{0,1,2\}^*$. 
The transitions in the Markov chain are the following:
$$
x 10 y \rightarrow x 01 y;~ 
x 20 y \rightarrow x 02 y;~ 
x 21 y \rightarrow x 12 y;~  
0 y \rightarrow 2 y;~
y 2 \rightarrow y 0;~  
$$
with rate $1$ and
$$
x 01 y \rightarrow x 10 y;~
x 02 y \rightarrow x 20 y;~ 
x 12 y \rightarrow x 21 y;~ 
$$
with rate $q$.
Note that the number of 1's
cannot change in the process and we denote it by $r$ henceforth.
An example of a chain on three letters among which two are equal to 1 is given on \cref{chain}.

\begin{figure}[h!t]\centering
  \includegraphics[width=0.50\textwidth]{chain.pdf}
  \caption{Chain for $N=3$ and $r=2$.}
  \label{chain}
\end{figure}

\subsection{Stationary distribution}

To each state $x$ of the 2-ASEP with $N$ sites we associate a word $X(x)$
in $\{A,D,E\}^N$ using the following map:
$$ 2\mapsto D;~ 1\mapsto A;~ 0\mapsto E. $$  

A segmented composition $\Ig$ codes the state $x$ if $\ade(\Ig) = X(x)$.

The usual way to compute the stationary distribution of the states of the 2-ASEP is to find some
matrices satisfying an Ansatz.

\begin{proposition}\cite{uchiyama}
  Let $D,A,E$ be infinite matrices. Let $\bra{W}$  (respectively $\ket{V}$) be an infinite row (respectively column)
  vector satisfying the Ansatz:
  \begin{eqnarray*}
    DE&=&qED+D+E; \ \ 
    DA=qAD+A;\ \
    AE=qEA+A\\
    \bra{W}E&=&\bra{W}; \ \
    D\ket{V}=\ket{V}.
  \end{eqnarray*}
  Then the probability to be in a state $x$ is:
  \begin{equation}
    \frac{\bra{W}X(x)\ket{V}}{[y^r]\bra{W}(D+yA+E)^N\ket{V}}.
    \label{stationProbaMat}
  \end{equation}
  where $[y^r]$ means that we consider the coefficient of the monomial $y^r$.
  \label{uchi}
\end{proposition}

\begin{remark}
  The Ansatz in~\cite{uchiyama} is more general. Here, we set $\alpha=\beta=1$
  and $\gamma=\delta=0$.
\end{remark}

We now give a new solution of this Ansatz.
Let $[n]_q=1+q+\ldots +q^{n-1}$ and
\begin{equation}
  \label{matDE}
  D=\begin{pmatrix}
  1  & 1 & 0 & 0&\ldots \\
  0  & [2]_q & [2]_q & 0& \ldots\\ 
  0  & 0 & [3]_q & [3]_q &  \ldots\\ 
  0  & 0 &  0 & [4]_q & \ldots\\ 
  \vdots & \vdots & \vdots & \vdots & 
  \end{pmatrix}; \ \ E=\begin{pmatrix}
  0  & 0 &  0 & 0  &   \ldots\\
  1  & 1 & 0 & 0& \ldots \\
  0  & [2]_q & [2]_q & 0& \ldots\\ 
  0  & 0 & [3]_q & [3]_q &  \ldots\\  
  \vdots & \vdots & \vdots & \vdots & 
  \end{pmatrix}
\end{equation}
\begin{equation}
  \label{matA}
  A=\mathbf{diag}(1,q,q^2,q^3,\ldots )(D+E);\ \
  \bra{W}=(1,1,0,0,\ldots);\ \ \ket{V}=(1,0,0,\ldots)^T. 
\end{equation}

\begin{lem}
  The previous matrices and vectors satisfy the equations in \cref{uchi}.
\end{lem}

One way to obtain a combinatorial interpretation of the stationary distribution is to interpret each monomial
of the numerator and denominator of~\eqref{stationProbaMat} as a weighted path.


\subsection{Path interpretation}

A Laguerre history is an object introduced by Viennot in~\cite{Vi}. The marked Laguerre histories are in bijection
with permutations through the Fran\c con-Viennot bijection~\cite{FV}. These
objects have often been used to study some properties of the ASEP \cite{JV}.

\begin{definition}
  A \emph{Laguerre history} $H$ of size $n$ is a weighted Motzkin path
  of size $n$ with two different horizontal steps such that
  \begin{itemize}
  \item a $\nearrow$ or $\longrightarrow$ step starting from height
    $h$ has a weight between 0 and $h$;
  \item a $\searrow$ or $\dashrightarrow$ step starting from height
    $h$ has a weight between 0 and $h-1$.
  \end{itemize}
  The \emph{weight} ${\rm wt}(H)$ of the Laguerre history is the sum of the weights of its steps.
\end{definition}

A {\em marked Laguerre history} of size $(n,r)$ is a Laguerre history of size $n$
where all the steps but the first can be marked and $r$ steps are marked.
Any marked step starting from height $h$ increases its weight by $h$.


An example of a marked Laguerre history of size $(8,2)$ is given in
\cref{chemin}. The steps with overlined weight are the marked steps.
We can associate labels with a marked Laguerre history. The marked steps are labeled
$A$, the $\nearrow$ or $\longrightarrow$ steps are labeled $D$ and the remaining steps
are labeled $E$. We forget the label of the first step. For example, the labels of the
marked Laguerre history on the right of \cref{chemin} are represented by the word
$ADADEDE$.

Given a word $X$, let $M(X)$ be the set of marked Laguerre histories 
with labels $X$ and let ${\mathcal Z}_X$ be the generating
polynomial of all the paths:
\begin{equation}
{\mathcal Z}_X(q)=\sum_{H\in M(X)} {q^{\rm wt}(H)};
\end{equation}
and let
\begin{equation}
{\mathcal Z}_{N,r}(q)=\sum_X {\mathcal Z}_{X}(q)
\end{equation}
where the sum is over all the words in $\{A,D,E\}^N$ with $r$ letters $A$. 

The following result gives us a combinatorial interpretation of \eqref{stationProbaMat}.
\begin{proposition}
  Given a word $X$ in $\{A,D,E\}^N$ with $r$ letters $A$,
  $$  \frac{{\mathcal Z}_{X}(q)}{{\mathcal Z}_{N,r}(q)}  $$
  is the stationary distribution of the state $X$ in the 2-ASEP with $N$ sites
  and $r$ particles of type~$1$.
  \label{probaChemin}
\label{read}
\end{proposition}

\begin{proof}
  The idea is to associate a marked Laguerre history with each monomial of the matrix product of
  the numerator of \eqref{stationProbaMat}. Any monomial corresponds to the
  product of $N$ non zero coefficients $(X_{k})_{i_k, j_k}$ where $X_k \in \{A, D, E\}$ is the
  matrix corresponding to the $k$-th letter of $X$.
  As the indices $(i_k, j_k)$ must satisfy $i_k = j_{k-1}$, they can represent the successive
  heights of a path. Moreover,
  as our matrices in~\eqref{matDE} are tridiagonal, $|i_k - j_{k}| \leq 1$ so
  the paths are Motzkin paths. In order to have a path starting from height $0$, we need to add
  a $\nearrow$ or
  $\longrightarrow$ step at the beginning of the path depending on which coefficient
  of $\bra{W}$ has been taken. For the steps labeled $D$, we have $j_k \in \{i_k, i_k+1\}$
  so the possible steps are $\nearrow$ or $\longrightarrow$, and for $E$, we have
  $j_k \in \{i_k, i_k-1\}$ so the possible steps are $\searrow$ or $\dashrightarrow$.

  The weight of the $k$-th step of the path corresponds to the power of $q$ taken in
  the coefficient $(X_{k})_{i_k, j_k}$. One can see that for the matrix $D$ (steps $\nearrow$ or
  $\longrightarrow$) the possible weights are between $0$ and $i_k$ and that for the matrix $E$
  (steps $\searrow$ or $\dashrightarrow$) the possible weights are between $0$ and $i_k-1$.
  Finally for the matrix $A$, the weights are the same than for $D$ and $E$ on which we added
  $i_k$ due to the $\mathbf{diag}(1,q,q^2,q^3,\ldots )$ factor. This proves that
  the paths we obtain are exactly the marked Laguerre histories.  
\end{proof}

Special cases of \cref{probaChemin} are:
\begin{equation}
  {\mathcal Z}_{N,r}(1)={N\choose r}(N+1)!; \ \
  {\mathcal Z}_{r,r}(q)=[r+1]_q!.
  \label{requalq}
\end{equation}
The first equation follows trivially from the next section
which exhibits a bijection between these marked Laguerre histories and partially signed permutations.
The second equation follows from a continued fraction proven by Heine. A bijective proof
was given by Biane~\cite{Bi}.


\subsection{From marked Laguerre histories to partially signed permutations}

We recall the Fran\c con-Viennot bijection~\cite{FV} that builds
a Laguerre history from a permutation $\sigma \in \SG_n$.
We denote  this map by $\psi_{FV}$.
We compare each value of the permutation $\sigma$ with its two neighbors.
We use the convention $\sigma_0 = 0$ and $\sigma_{n+1} = n+1$. We denote by
$H_k$ the $k$-th step of the Laguerre history $H$.

\begin{algo}
  \label{algoFV}
  Let $\sigma \in \SG_n$, $k \in \{1, \ldots, n\}$, and $j$ such that $\sigma_j=k$. Then, in
  the Laguerre history~$H=\psi_{FV}(\sigma)$ we have
  \begin{itemize}
  \item $H_{k} =~ \nearrow$  if $\sigma_j$ is a \emph{valley},
    \ie, $\ssig_{j-1} > \sigma_j < \sigma_{j+1}$,
  \item $H_{k} =~ \searrow$ if $\sigma_j$ is a \emph{peak},
    \ie, $\ssig_{j-1} < \sigma_j > \sigma_{j+1}$,
  \item $H_{k} =~ \longrightarrow$  if $\sigma_j$ is a \emph{double rise},
    \ie, $\ssig_{j-1} < \sigma_j < \sigma_{j+1}$,
  \item $H_{k} =~ \dashrightarrow$ if $\sigma_j$ is a \emph{double descent},
    \ie, $\ssig_{j-1} > \sigma_j > \sigma_{j+1}$.
  \end{itemize}
  The weight $w$ is constructed as follows: $w_k$ is equal to the number of $\312$ 
  patterns such that $k$ is the number corresponding to~$2$ in $\ssig$.
\end{algo}

Now to generalize this to partially signed permutations, let $\ssig \in B_n'$.
Apply the above bijection without considering the signs. For each
$\overline{i} \in \ssig$, mark the $i^{\text{th}}$ step of the Laguerre
history. When we mark a step starting at height $h$, we increase its weight by $h$.
We denote by $\psi_{FV}(\ssig)$ the result of this algorithm.

For example, for $\ssig=\overline{2}57836\overline{4}1$,
the image of $\ssig$ without the signs is given on the left of \cref{chemin}
and the marked version is on its right.

\begin{figure}[h!t]\centering
  \includegraphics[width=0.95\textwidth]{chemin.pdf}
  \caption{(Marked) Laguerre histories.}
  \label{chemin}
\end{figure}

\begin{proposition}
  The generalization of the Fran\c con-Viennot bijection is a bijection between
  partially signed permutations of size $n$ with $r$ overlined values
  and marked Laguerre histories of size $n$ with $r$ marked steps.
  The bijection is such that the number of $\312$ patterns plus the number of
  $(31, \overline{2})$ patterns of the partially signed permutation
  is equal to the weight of the history. Moreover, if $\ssig \in B_n'$, then
  $\ade(\GC(\ssig))$ is the same as the labels of $\psi_{FV}(\ssig)$.
  \label{propFV}
\end{proposition}

To prove this proposition, one has to use the inverse of Fran\c con-Viennot bijection and
see that the patterns $(31, \overline{2})$
correspond to the $\312$ patterns that would be created if $\overline{2}$ was also
placed at the end of $\ssig$.

Using \cref{probaChemin} and \cref{propFV} we can deduce 
\cref{probaPerm}.

\begin{remark}
  If we take the inverse of the signed permutations in $B'$ we obtain another subclass of $B$
  which are the signed permutations where the first value is not signed. The obtained statistic
  corresponds to the notion of ascent defined in~\cite{MV}. The number of these permutations
  with $r$ overlined values are $(r+1)!$ times the
  number of assembl\'ees of permutations.
  Moreover, our
  polynomials ${\mathcal Z}_X(q)$ and ${\mathcal Z}_{n,r}(q)$ are equal to $[r+1]_q !$ times the
  polynomials of~\cite{MV}.
  \label{remOlya}
\end{remark}

\section{Combinatorial algebras}
\label{algebre}

The statistics $\GC$ on permutations is used to give a combinatorial interpretation of
the stationary distribution of the ASEP~\cite{SW}.
This statistic also appeared in a totally different framework. When Tevlin defined a new basis of
$\NCSF$~\cite{T}, $\GC$  appeared in the computation of the transition matrices
of this new basis to the ribbon basis. In this section we transpose
the work of~\cite{HNTT} into our context of partially signed permutations to generalize Tevlin's basis to the algebra
of segmented compositions $\SCQSym$.

\subsection{The algebra of partially signed permutations}

There are several ways to generalize the permutation algebra~$\FQSym$.
One of them is the \emph{signed permutation algebra} $\SFQSym$~\cite{SFQSYM}.
Here we define an algebra indexed by the partially signed permutations
$\GPQSym$ as a subalgebra of $\SFQSym$.

Since an element $\ssig$ of $B_n'$ does not have a sign on $1$, this
element can be viewed as the sum of two signed permutations $\overline{\ssig}$ and
$\widetilde{\ssig}$ which correspond to $\ssig$ where we respectively put a plus sign
and a minus sign on 1.

\begin{definition}
  The algebra $\GPQSym$ is the subalgebra of $\SFQSym$ spanned by the relations
  \begin{equation}
    \FGP_\ssig := \FSP_{\overline{\ssig}} + \FSP_{\widetilde{\ssig}},
  \end{equation}
  for $\ssig \in B_n'$ 
  where $(\FSP_\tau)$ is the fundamental basis of $\SFQSym$.
\end{definition}

For a word $w$, denote by $w[k]$ the word obtained by replacing each letter $i$ by
the integer $i+k$. If $\ssig$ and $\ttau$ are two elements of $B'$, one defines the
\emph{shifted shuffle} on partially signed permutations.
\begin{equation}
  \ssig\ssh \ttau= \ssig\shuffle (\overline{\ttau}[k]) + \ssig\shuffle (\widetilde{\ttau}[k]),
\end{equation}
where $k$ is the size of $\ssig$ and $\shuffle$ is the usual shuffle product
on words defined by
\begin{equation}
  (au)\shuffle (bv) = a\cdot(u\shuffle (bv)) + b\cdot ((au)\shuffle v),
\end{equation}
with $u\shuffle\epsilon=\epsilon\shuffle u=u$ if $\epsilon$ is the empty word.

The product formula of two $\FGP_\ssig$ given in \cref{producFormula}
follows directly from the shifted shuffle over signed permutations.

\subsection{The algebra of segmented compositions}

In~\cite{NT} the authors introduced the algebra
of segmented compositions~$\SCQSym$ generalizing the algebra of non commutative symmetric
functions~$\NCSF$. Indeed, when $\NCSF$ can be viewed as the algebra of the vertices of the hypercube,
$\SCQSym$ is the algebra of all the faces of the hypercube.

This algebra has a ribbon basis $(\RSC_\Ig)$ satisfying the following product formula
\begin{equation}
  \RSC_\Ig \cdot \RSC_{\Jg} = \RSC_{\Ig \cdot \Jg} + \RSC_{\Ig |\Jg}
  + \RSC_{\Ig \triangleright\Jg}.
\end{equation}
Given $\Ig = (i_1, \ldots, i_s)$ and
$\Jg = (j_1, \ldots, j_k)$ where the separators are either bars or commas, define
\begin{equation}
  \begin{array}{rcl}
  \Ig \cdot \Jg & := & (i_1, \ldots, i_s, j_1, \ldots, j_k), \\
  \Ig |\Jg & := & (i_1, \ldots, i_s| j_1, \ldots, j_k),\\ 
  \Ig \triangleright\Jg & := & (i_1, \ldots, i_s + j_1, \ldots, j_k).
  \end{array}
  \end{equation}
For example, $ \RSC_{(2|1)} \cdot \RSC_{(1,3)} =  \RSC_{(2|1,1,3)} + \RSC_{(2|1|1,3)} + \RSC_{(2|2,3)}$.

Just as $\NCSF$ is a subalgebra of \FQSym, it can be shown that $\SCQSym$ is
subalgebra of $\GPQSym$ algebra with the following identification given in \cref{injRF}.
\begin{equation}
  \RSC_\Ig = \sum_{\Rec(\ssig) = \Ig}\FGP_\ssig\ .
  \label{eqSumRF}
\end{equation}
\subsection{Analogue of the basis of Tevlin}

Let $\sim$ be the equivalence relation defined by~$\ssig \sim {\bm \tau}$ if and only
if~$\GC(\ssig) = \GC({\bm \tau})$.
Let ${\cal J}$ be the subspace of $\GPQSym$ spanned by the differences
\begin{equation}
  \{ \FGP_\ssig - \FGP_{\bm \tau}~|~\ssig \sim {\bm \tau} \}.
\end{equation}

If $\Ig$ and {\bf J} be two segmented compositions, we say that $\Ig$ is finer than ${\bf J}$ (or
${\bf J}$ is coarser than $\Ig$) if and only if
they have the same size, $\Des(\Ig) \subseteq \Des({\bf J})$,
and $\Des(\Ig)$ has the same overlined values as $\Des({\bf J})$.

\begin{proposition}
  ${\cal J}$ is a two-sided ideal of $\GPQSym$, and the
  quotient~${\bf T} = \GPQSym / {\cal J}$ is isomorphic to $\SCQSym$ as an algebra.
\end{proposition}

We have a map $\phi$ from $\SCQSym$ to itself that can be described as follows.

\begin{equation}
  \begin{array}{ccccccc}
    \SCQSym &  \hookrightarrow & \GPQSym & \twoheadrightarrow & {\bf T} & \leftrightarrow & \SCQSym \vspace{0.2cm}\\
    \RSC_\Ig & \mapsto & \sty \sum_{\Rec(\ssig) = \Ig}\FGP_\ssig &&&& \\
    & & \hspace{1.5cm} F_\ssig & \mapsto & T_{\GC(\ssig)} & \mapsto & L_{\GC(\ssig)}
  \end{array}
\end{equation}

This map $\phi$ is an isomorphism of algebras. Define
$L_\Ig$ as the image of $\FGP_\ssig$ in $\SCQSym$.

\begin{thm}
  Let $\Ig$ and $\Jg$ be two segmented compositions,
  \begin{equation}
    L_\Ig L_{\bf J} = \sum_{\bf K} C_{\bf I,J}^{\bf K} L_{\bf K},
  \end{equation}
  where $C_{\bf I,J}^ {\bf K}$ is computed as follows.
  Let ${\bf K}'$ and ${\bf K}''$ be the segmented compositions such that $|{\bf K}'|=|\Ig|$
  and either
  ${\bf K}={\bf K}'\cdot {\bf K}''$, ${\bf K}={\bf K}'\triangleright {\bf K}''$,
  or ${\bf K}={\bf K}'| {\bf K}''$.
  If ${\bf K}'$ is not coarser than $\Ig$ or if ${\bf K}''$ is not finer than ${\bf J}$, then
  $C_{\Ig,{\bf J}}^{\bf K}$ is $0$.
  Otherwise, we have
  \begin{equation}
    C_{\Ig,{\bf J}}^{\bf K}= \binomial{|\Ig|+e({\bf J})-e(\Ig)+a({\bf K})-a(\Ig)}
    {l({\bf K})-l(\Ig)},
  \end{equation}
  where $a(\Ig)$ is the number of bars in $\Ig$, $e(\Ig)$ is the number of values in
  $\Ig$ minus the number of bars, and $l(\Ig)$ is the number of values in $\Ig$.
  \label{thCoeff}
\end{thm}

The proof of this theorem follows the same ideas as the proof of Theorem 4.1. in~\cite{HNTT}.

\subsection{Transition matrices}

Identifying each $\RSC_\Ig$ and its image under the map $\phi$, we have the following result. 

\begin{thm}
  Let $\Ig$ be a segmented composition of $n$. Then
  \begin{equation}
    \RSC_\Ig = \sum_{{\bf J}}G_{\Ig \bf J}L_{\bf J},
  \end{equation}
  where $G_{\bf I J}$ is the number of partially signed permutations $\ssig$ satisfying $\Rec(\ssig) = \Ig$
  and $\GC(\ssig) = {\bf J}$. In particular, the $G_{\bf I J}$ are non negative integers.
  \label{thChangeBasis}
\end{thm}

In addition to this result, the transition matrices from $\RSC$ to $L$ have some other interesting
properties. Here is the transition matrix for $n=3$. For better readability, 0 has been represented
by a dot.
$$
\left(\begin{array}{rrrr|rr|rr|r}
1 & . & . & . & . & . & . & . & . \\
. & 2 & 1 & . & . & . & . & . & . \\
. & . & 1 & . & . & . & . & . & . \\
. & . & . & 1 & . & . & . & . & . \\ 
\hline \vspace{-0.5cm}\\
. & . & . & . & 3 & 1 & . & . & . \\
. & . & . & . & . & 2 & . & . & . \\
\hline \vspace{-0.5cm}\\
. & . & . & . & . & . & 2 & . & . \\
. & . & . & . & . & . & 1 & 3 & . \\
\hline \vspace{-0.5cm}\\
. & . & . & . & . & . & . & . & 6
\end{array}\right)
$$

\cref{remNbA} implies that the matrix is  block diagonal. It is also straightforward
to see that the top left block is the transition matrix obtained in the permutation case~\cite{HNTT}
and that the sum of
the values in each block is $n!$.
It is also possible to prove that each value (except of the first block) are the sum of four other values in
some blocks of bigger size.


\section{Conclusion and acknowledgments}

This work can be generalized in several ways. First  we can define a monomial basis for $\SCQSym$ and
define a $q-$analogue of some bases of this algebra. This uses the theory of segmented packed words. It
gives an enumaration formula for ${\mathcal Z}_X(q)$.

The $2-$ASEP defined in~\cite{uchiyama} has four other parameters and two of them could also be interpreted
in term of statistics on Laguerre histories. All this will be addressed in the long version of this
extended abstract.

The authors want to thank Jean-Christophe Novelli for his advice during the elaboration of this work and
the members of the GT-combalg for their reading of the manuscript and their constructive comments.

\printbibliography



\end{document}
